package lk;

public class D230927 {
    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }


    // 删除链表的中间节点
    // 快慢指针寻找中间节点，同时记录中间节点的前一个节点
    // 时间：O(n)
    // 空间：O(1)
    public ListNode deleteMiddle(ListNode head) {
        if (head.next == null) {
            return null;
        }
        ListNode pre = null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = slow.next;
        return head;
    }


    // 奇偶链表

    // 使用三个指针，cur 用来遍历奇数位节点，
    // pre 用来记录 cur 的前一个结点，cur 头插到 odd 后
    // 时间：O(n)
    // 空间：O(1)
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode odd = head;
        ListNode pre = head.next;
        ListNode cur = head.next.next;
        while (cur != null && cur.next != null) {
            ListNode curNext = cur.next;
            cur.next = odd.next;
            odd.next = cur;
            pre.next = curNext;

            odd = cur;
            pre = curNext;
            cur = curNext.next;
        }
        if (cur != null) {
            cur.next = odd.next;
            odd.next = cur;
            pre.next = null;
        }
        return head;
    }

    // 维护一个奇数链表，一个偶数链表
    // 最终将两个链表连接在一起
    // 时间：O(n)
    // 空间：O(1)
    public ListNode oddEvenList2(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode evenHead = head.next;
        ListNode odd = head, even = evenHead;
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }


    // 反转链表
    // 使用头插法反转链表
    // 时间：O(n)
    // 空间：O(1)
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }


    // 链表最大孪生和
    // 时间：O(n)
    // 空间：O(1)
    public int pairSum(ListNode head) {
        // 1. 找到中间节点
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode mid = slow;
        // 2. 从中间节点开始, 使用头插法反转链表
        ListNode pre = null;
        while (slow != null) {
            ListNode next = slow.next;
            slow.next = pre;
            pre = slow;
            slow = next;
        }
        // 从两端遍历链表, 记录最大孪生和
        int res = 0;
        while (head != mid) {
            res = Math.max(res, head.val + pre.val);
            head = head.next;
            pre = pre.next;
        }
        return res;
    }
}
